% DO NOT COMPILE THIS FILE DIRECTLY!
% This is included by the other .tex files.

%\section*{Outline}
%\frame{\tableofcontents}

\section{Introduction}

%2
\begin{frame}[t,fragile]{\textbf{Swarm Robotics}}
\vfill
\begin{large}
\begin{flushleft}
\emph{"Swarm robotics is the study of how large number of \textbf<3>{relatively simple physically embodied agents} can be \textbf<2>{designed} such that a desired \textbf<4>{collective behavior emerges from} the \textbf<4>{local interactions} among agents and between the agents and the environment."
}
\end{flushleft}
\end{large}
\begin{flushright}
from \cite{csahin2005swarm}
\end{flushright}


\note{
\only<1>{Test}
\only<2>{Design = Engineering problem.

Indeed, the main research question in Swarm Robotics (SR) is how
to develop design methodologies at the individual level that will
cause the emergence of a collective behavior exhibiting the aforemen-
tioned properties.
The systematic application of scientific and technical knowledge in a
structured way in the development process is generally referred as
Swarm Engineering.
}
\only<3>{Relatively simple physically embodied agents = Robots.

A physical embodied agent is an entity whose behavior is affected
by its morphological features and the environment it is situated in.
In order for the agent to be embodied, it must
be able to transfer and process matter, energy (through its actuators)
and information (by means of its sensors and its internal architecture),
hence it must be a robot.

}
\only<4>{Collective behavior emerges from local interactions among agents and between the agents and the environment = Self-organization.

"Self-organization is a process in which pattern at the global
level of a system emerges solely from numerous interactions
among the lower-level components of the system.
Moreover, the rules specifying interactions among the system’s
components are executed using only local information, without
reference to the global pattern."

}
}
\end{frame}

%3
\begin{frame}[t,fragile]{\textbf{Robot characteristics}}
\vskip30pt
\begin{large}
\begin{itemize}
\item<2-> Autonomy \only<6>{$\Rightarrow$ Lack of centralized control}
\vskip10pt 
\item<3-> Embodiment
\vskip10pt
\item<4-> Local sensing and communication capabilities \only<7>{$\Rightarrow$ Lack of global knowledge}
\vskip10pt
\item<5-> Cooperation
\end{itemize}
\end{large}
\note{Embodiment = Robot are situated in the environment and can act to modify it

Cooperation and self-organization are the mechanisms that cause the emergence of a collective behavior.}
\end{frame}

%4
\begin{frame}[t,fragile]{\textbf{Why Swarm Robotics?}}
\begin{large}
\vskip30pt
Social animals societies with similar characteristics exhibit:
\vskip15pt
\begin{itemize}
\item<2-> Flexibility
\vskip10pt 
\item<3-> Scalability
\vskip10pt
\item<4-> Robustness
\end{itemize}
\end{large}
\note{

Advantageous properties.

\textbf{Robustness} is the ability to cope with the loss of individuals. 
In social animals,robustness is promoted by redundancy and the absence of a leader. 


\textbf{Scalability} is the ability to perform well with different group sizes. The introduction or removal of individuals does not result in a drastic change of the performance of a swarm. In social animals, scalability is promoted by local sensing and communication. 


\textbf{Flexibility} is the ability to cope with a broad spectrum of different environments and tasks. In social animals, flexibility is promoted by redundancy, simplicity of the behaviors and mechanisms such as task allocation.

We would like to design a system possessing the same characteristics.}


\end{frame}

%5
\begin{frame}[t,fragile]{\textbf{Spatial Allocation}}
\vfill
\begin{tikzpicture}[scale=0.8]  
    \path[mindmap,concept color=black,text=white,text centered]
    node[concept,scale=0.7] {Spatial\\ Allocation}
    child[grow=-135,concept color=green!50!black, visible on=<2->] {
      node[concept,scale=0.7] {Multi-robot task allocation}
    }
    child[grow=-45,concept color=blue, visible on=<4->] {
      node[concept,scale=0.7] {Collective foraging}
    };
    
  \only<1->{\node [draw,rectangle,text width=3.5cm,rounded corners,thick,color=black,text=black,text centered] (spaAlloc) at (8,0) {%
	 \textbf{Spatial Allocation}
	 \vskip7pt
	 {\footnotesize Allocation of embodied agents to physical tasks localized in space.} 
  };}  
  \only<2-3>{\node [draw,rectangle,text width=3.5cm,rounded corners,thick,color=green!50!black,text=black, text centered] (taskAlloc) at (8,-3.5) {%
	  \textbf{Task allocation}
	   \vskip7pt
	 {\footnotesize Allocation of swarm of embodied agents to different activities, \only<2>{known a priori}\only<3>{\st{known a priori}}.}
       };}
  \only<4->{\node [draw,rectangle,text width=3.5cm,rounded corners,thick,color=blue,text=black,text centered] (Foraging) at (8,-3.5) {%
	  \textbf{Foraging}
	  \vskip7pt
	  \begin{footnotesize}
	  \begin{enumerate}
	  \item<4-5> Resource localization
	  \item<4-5> Resource collection
	  \item<4-5> \only<4>{Navigation} \only<5>{\st{Navigation}} 
	  \item<4-5> \only<4>{Deposit} \only<5>{\st{Deposit}} 
	  \end{enumerate}
	  \end{footnotesize}
  };}
    
  
 
\end{tikzpicture}
\end{frame}


\section{Problem statement}

%6
\begin{frame}[t,fragile]{\textbf{Problem statement}}
\vskip30pt
\begin{large}
\begin{flushleft}
\begin{definition}
Given n \textbf<2>{robots} and m \textbf<3>{tasks} grouped in space, design a distributed algorithm capable of achieving an allocation of the robots to the tasks which is as uniform as possible across groups.
\end{definition}
\end{flushleft}
\end{large}
\only<2>{
\begin{itemize}
\item Identical
\end{itemize}
}
\only<3>{
\begin{itemize}
\item Homogeneous
\item Independent
\item $m > n$
\end{itemize}
}
\note{Furthermore, robots are assumed to be identical
among them and tasks are considered homogeneous (i.e. there are no
difference among tasks in terms of required skills to be performed)
and independent (i.e. there are no relations among the tasks) of each
other.
}
\end{frame}


%7
\begin{frame}[t,fragile]{\textbf{Problem implementation}}
\begin{center}
\begin{tikzpicture}[scale=1.5]
	
	%Bounding box
    \only<1->{\draw[black,ultra thick](-2,2) rectangle (2,-2);}
	
    % Clusters
    \only<2->{
    \draw[black,thick](1,1) circle [radius=0.3];
    \draw[black](1,1) node(Cluster1){1};
    \draw[black,thick](-1,1) circle [radius=0.3];
    \draw[black](-1,1) node(Cluster2){2};
    \draw[black,thick](-1,-1) circle [radius=0.3];
    \draw[black](-1,-1) node(Cluster3){3};
    \draw[black,thick](1,-1) circle [radius=0.3];
    \draw[black](1,-1) node(Cluster4){4};}
    
    %Deployment area    
    \only<3->{\draw[dashed,black,fill=green!20] (-0.5,0.5) rectangle (0.5,-0.5);}
    
    %Robots
   \only<4->{\def\xlist{4}
	\def\ylist{4}
	\pgfmathsetmacro\diameter{0.05*2}    
    \foreach \i in {1,2,...,20}
    {
      \pgfmathsetmacro\x{rnd-0.5}
      \pgfmathsetmacro\y{rnd-0.5}
      \xdef\collision{0}
      \foreach \element [count=\i] in \xlist{
       		\pgfmathtruncatemacro\j{\i-1}
            \pgfmathsetmacro\checkdistance{ sqrt( ({\xlist}[\j]-(\x))^2 + ({\ylist}[\j]-(\y))^2 ) }
            \ifdim\checkdistance pt<\diameter pt
                \xdef\collision{1}
                \breakforeach
            \fi
        }
        \ifnum\collision=0
            \xdef\xlist{\xlist,\x}
            \xdef\ylist{\ylist,\y}
            \draw[fill=black!20] (\x,\y) circle [radius=0.05];
        \fi 
    }}
    
    %Legend   
	\only<2->{\draw [black] (3,0.5) circle (.15cm) node(cluster) [right=-0.17] {i~~~Working area};}	
	\draw [dashed,black,fill=green!20,visible on=<3->] (2.9,-0.1) rectangle (3.1,0.1); 
	\node [visible on=<3->] at (4.19,0) {Deployment area};	
	\only<4->{\draw [fill=black!20] (3,-0.5) circle (.05cm) node(robot) [right=0.18cm] {~Robot};}
	%\node [draw,rectangle,text width=5cm,rounded corners,thick,fit=(3,0.7) (5,-0.7)] (TAM) {};
   
\end{tikzpicture}
\end{center}

\note{
Working area with unitary requests
}

\end{frame}

%8
\begin{frame}[t,fragile]{\textbf{Working areas}}
\vfill
\begin{minipage}{.59\textwidth}
\centering
\begin{tikzpicture}[scale=3]
\draw [dashed,fill=blue!20] (0,0) circle (.75cm);
\foreach \x in {45,90,135,180,270,315}
    {
    \draw (0:0.42cm) [rotate=\x,fill=green!20,very thick] +(-.12,-.12) rectangle ++(.12,.12);
    %\draw (\x:0.5cm) node{\x};
    }
\foreach \x in {225,360}
    {
    \draw (0:0.42cm) [rotate=\x,fill=red!40,very thick] +(-.12,-.12) rectangle ++(.12,.12);
    %\draw (\x:0.5cm) node{\x};
    }
%\node [draw,rectangle,text width=5cm,rounded corners,thick,text=black] (TAM) at (0,-1.1) {%  	   
%   \begin{footnotesize}
%   	\vskip3pt
%   	%~~~~ TAM ~~~~~~ Sensing range\\
%   	~
%	\end{footnotesize}     
%    };
\draw [fill=green!20,very thick] (-0.70,-1.15) rectangle (-0.60,-1.05);
\node at (-0.4,-1.1) {Free};
\draw [fill=red!40,very thick] (-0.70,-1.35) rectangle (-0.60,-1.25);
\node at (-0.28,-1.3) {Occupied}; 
\draw [dashed,fill=blue!20] (-0.05,-1.10) circle (.07cm) node [right=0.17cm] {Sensing range};
\end{tikzpicture}
\end{minipage}%
\hspace{0.15cm}
\begin{minipage}{.35\textwidth}
Each working area $i$ is characterized by:
\begin{itemize}
\item Request: $r_i$ 
\item Occupation: $o_i(t)$
\item Error: $e_i(t) = r_i - o_i(t)$
\end{itemize}
\vfill
\end{minipage}

\note{
Sensing range for information exchange about the cluster state.
}

\end{frame}


\section{Methodology}

%9
\begin{frame}[t,fragile]{\textbf{IRIDIA TAM \& e-puck}}
\begin{tikzpicture}
    \node[anchor=south west,inner sep=0] (image) at (0,0) {\includegraphics[width=0.7\textheight]{../Gfx/tam_v4_simple_epuck.jpg}};
    \only<1-5>{
    \node [draw,rectangle,text width=4.5cm,rounded corners,thick,color=red,text=black] (ePuck) at (9,3) {%
	\begin{center}
	\textbf{E-puck}
	\end{center}
	\begin{footnotesize}
	Omnidirectional camera
	\vskip7pt   	
   	Range and Bearing system	
	\vskip7pt   	
   	Proximity sensors   	
   	\vskip7pt
   	Wheels
   	\vskip5pt
   	~
	\end{footnotesize}	   	
    };}
    
    \only<6->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color= green!50!black,text=black] (TAM) at (9,3) {%
	\begin{center}
	  \textbf{TAM}
	  
	  {\footnotesize \textbf{Task Abstraction Module}}
	  \end{center}  
   \begin{footnotesize}
   	LEDs
   	\vskip7pt
   	Light barriers
   	\vskip7pt
    Local communication
    \vskip5pt
    ~
	\end{footnotesize}     
    };}
    
    \begin{scope}[x={(image.south east)},y={(image.north west)}]
		\node (ePuckWheels) at (0.33,0.2) {};    	
    	\node (ePuckProximity) at (0.41,0.29) {};
    	\node (ePuckRab) at (0.45,0.415) {};
    	\node (ePuckOmnicamera) at (0.25,0.57) {};
    	\node (tamLED) at (0.6,0.5) {};
    	\node (tamLight) at (0.77,0.32) {};
    	
    	
		\only<3>{\draw [decorate,thick,red,decoration={brace,amplitude=2pt,mirror,raise=1pt},yshift=0pt]
				 (0.45,0.39) -- (0.45,0.44);}    	 	
    	 %\draw[red,ultra thick,rounded corners] (0.62,0.65) rectangle (0.78,0.75);
    \end{scope}
	 
	 \only<2>{\draw [->,thick,red] (6.62,3.65) -- (ePuckOmnicamera);}
	 \only<3>{\draw [->,thick,red] (6.62,2.95) -- (ePuckRab);}
	 \only<4>{\draw [->,thick,red] (6.62,2.35) -- (ePuckProximity);}
     \only<5>{\draw [->,thick,red] (6.62,1.75) -- (ePuckWheels);}
     \only<7>{\draw [->,thick,green!50!black] (6.62,3.10) -- (tamLED);}
     \only<8>{\draw [->,thick,green!50!black] (6.62,2.40) -- (tamLight);}   
    %\draw[help lines,xstep=.5,ystep=.5] (image.south east) grid (image.north west);

\end{tikzpicture}
%\begin{scriptsize}
%\begin{tikzpicture}[scale=0.5,shorten >=1pt,node distance=2.5cm,on grid,auto]
%   \node[state,thick,draw=green!75,fill=green!20,] (Av)   {Available}; 
%	\node[state,initial,thick,draw=orange!75,fill=orange!20,] (Dis) [above=of Av]   {Disabled};   
%   \node[state,thick,draw=red!75,fill=red!20] (Oc) [below=of Av ] {Occupied}; 
%   %\node[state,thick,draw=yellow!75,fill=yellow!20] (Un) [right=of Av] {Unavailable};
%    \path[->] 
%    (Av) edge node [text width=1.5cm] {Sense Robot} (Oc)
%	(Dis) edge node  {Enabled} (Av);
%    %(Oc) edge [bend left]  node  {$T_w$ expired} (Un)
%    %(Un) edge [bend left] node [left]  {Robot not sensed} (Av);
%\end{tikzpicture}
%\end{scriptsize}
\end{frame}

%10
\begin{frame}[t,fragile]{\textbf{Contribution summary}}
\begin{itemize}
\vskip10pt
\item<1-> Methods
	\begin{itemize}
	\item Naive
	\item Probabilistic
	\item Informed
	\end{itemize}
\vskip10pt
\item<2-> Scenarios
	\begin{itemize}
	\item Uniform
	\item Biased
	\item Corridor	
	\end{itemize}
\vskip10pt
\item<3-> Measures
	\begin{itemize}
	\item Allocation uniformity
	\item Allocation speed
	\end{itemize}
\end{itemize}

\end{frame}

%11
\begin{frame}[t,fragile]{\textbf{Methods overview}}
\begin{center}
\begin{scriptsize}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto] 
   \only<1>{\node[state,initial,thick] (Ex)   {Exploration};}
   \only<2->{\node[state,initial,red,text=black,thick] (Ex)   {Exploration};} 
   \node[state] (As) [below right=of Ex,text width=1.3cm,text centered,thick] {Assessing working area}; 
   \node[state,accepting,thick] (Uw) [below left=of Ex] {Allocation};
   \only<1-2>{\node[state,thick] (De) [below left=of As] {Decision};}
   \only<3->{\node[state,green!50!black,text=black,thick] (De) [below left=of As] {Decision};}
    \path[->] 
    (Ex) edge [bend left]  node  {Sense task} (As)
    (As) edge [bend left,text width=2cm]  node  {Within information sensing range} (De)
    (De) edge node [below,rotate=90,text width=2.3cm]  {Working area full $\vee$ Not allocate} (Ex) 
         edge [bend left] node {Allocate} (Uw);
\end{tikzpicture}
\end{scriptsize}
\end{center}
\note{The communication among the TAM and the robot is performed visually, with the TAM displaying its internal state by means of LEDs, whose color can be detected by the the robots' omnidirectional camera.

In the assessing phase, the robot exchanges information with the working area regarding the request and the current occupation.

The allocation phase consist in stopping the robot inside the TAM, to simulate the execution of a task.}
\end{frame}

%12
\begin{frame}[t,fragile]{\textbf{Naive}}
\begin{scriptsize}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto] 
   \node[state,initial,red, text=black,thick] (Ex)   {Exploration}; 
   \node[state,thick] (As) [below right=of Ex,text width=1.3cm,text centered,thick] {Assessing cluster}; 
   \node[state,accepting,thick] (Uw) [below left=of Ex] {Allocation};
   \node[state,green!50!black,text=black,thick] (De) [below left=of As] {Decision};
   \only<2->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color=red,text=black,text centered] (ExDetails) at (6,0) {%
	\begin{center}
	\textbf{Exploration policy}
	\end{center}
	Uninformed random walk		    
    };}
    \only<3->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color= green!50!black,text=black] (AllocDetails) at (6,-4) {%
	\begin{center}
	\textbf{Allocation policy}
	\end{center}    
    Greedy.
    
    Leave if at time $t^*$, $r_i(t^*)=o_i(t^*)$.
    };}
    \path[->] 
    (Ex) edge [bend left]  node  {Sense task} (As)
    (As) edge [bend left,text width=2cm]  node  {Within information sensing range} (De)
    (De) edge node [below,rotate=90,text width=2cm]  {Cluster full $\vee$ Not allocate} (Ex) 
         edge [bend left] node {Allocate} (Uw);
\end{tikzpicture}
\end{scriptsize}
\end{frame}

%13
\begin{frame}[t,fragile]{\textbf{Probabilistic}}
\begin{scriptsize}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto] 
   \node[state,initial,red, text=black,thick] (Ex)   {Exploration}; 
   \node[state,thick] (As) [below right=of Ex,text width=1.3cm,text centered,thick] {Assessing working area}; 
   \node[state,accepting,thick] (Uw) [below left=of Ex] {Allocation};
   \node[state,green!50!black,text=black,thick] (De) [below left=of As] {Decision};
   \only<2->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color=red,text=black,text centered] (ExDetails) at (6,0) {%
	\begin{center}
	\textbf{Exploration policy}
	\end{center}
	Uninformed random walk		    
    };}
    \only<3->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color= green!50!black,text=black] (AllocDetails) at (6,-4) {%
	\begin{center}
	\textbf{Allocation policy}\\
	\textbf{at time} $\mathbf{t^*}$
	\end{center}    
    Probabilistic with abandon 
    
    probability $a_i(t^*)=\frac{o_i(t^*)}{r_i(t^*)}$. 

	Probabilistic stalemate prevention rule. 

	Leave if $r_i(t^*)=o_i(t^*)$.
    };}
    \path[->] 
    (Ex) edge [bend left]  node  {Sense task} (As)
    (As) edge [bend left,text width=2cm]  node  {Within information sensing range} (De)
    (De) edge node [below,rotate=90,text width=2.3cm]  {Working area full $\vee$ Not allocate} (Ex) 
         edge [bend left] node {Allocate} (Uw);
\end{tikzpicture}
\end{scriptsize}
\note{The physical embodiment of the robots makes the occurrence of an obstruction phenomenon possible.
In fact, if two robots decides to direct towards the same task, it may occur that the two robots will prevent one another from reaching the chosen activities.
From here the necessity of a probabilistic stalemate avoidance rule to break such kind of ties.}
\end{frame}

%14
\begin{frame}[t,fragile]{\textbf{Informed}}
\begin{scriptsize}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto] 
   \node[state,initial,red, text=black,thick] (Ex)   {Exploration}; 
   \node[state,thick] (As) [below right=of Ex,text width=1.3cm,text centered,thick] {Assessing working area}; 
   \node[state,accepting,thick] (Uw) [below left=of Ex] {Allocation};
   \node[state,green!50!black,text=black,thick] (De) [below left=of As] {Decision};
   \only<3->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color=red,text=black,text centered] (ExDetails) at (6,0) {%
	\begin{center}
	\textbf{Exploration policy}
	\end{center}
	Informed random walk 
	
	using odometry		    
    };}
    \only<2->{\node [draw,rectangle,text width=4.5cm,rounded corners,thick,color= green!50!black,text=black] (AllocDetails) at (6,-4) {%
	\begin{center}
	\textbf{Allocation policy}\\
	\textbf{at time} $\mathbf{t^*}$	
	\end{center}    
    Probabilistic with abandon 
    
    probability $a_i(t^*)=\frac{o_i(t^*)}{r_i(t^*)}$. 

	Probabilistic stalemate prevention rule. 

	Leave if $r_i(t^*)=o_i(t^*)$.
    };}
    \path[->] 
    (Ex) edge [bend left]  node  {Sense task} (As)
    (As) edge [bend left,text width=2cm]  node  {Within information sensing range} (De)
    (De) edge node [below,rotate=90,text width=2.3cm]  {Working area full $\vee$ Not allocate} (Ex) 
         edge [bend left] node {Allocate} (Uw);
\end{tikzpicture}
\end{scriptsize}
\note{Explain how the odometry is used: To prevent robot from going back to recently left clusters.}
\end{frame}

%15
\begin{frame}[t,fragile]{\textbf{Scenario}}
\vfill
\begin{minipage}{.31\textwidth}
\centering
\begin{tikzpicture}[scale=0.8]
    \draw[dashed,black,fill=green!20] (-0.5,0.5) rectangle (0.5,-0.5);    
    \draw[black,very thick](-2,2) rectangle (2,-2);
      

    % Clusters
    \cluster{Cluster1}{1}{(1, 1)};
	\cluster{Cluster2}{2}{(-1, 1)};
	\cluster{Cluster3}{3}{(-1, -1)};	
	\cluster{Cluster4}{4}{(1, -1)};
\end{tikzpicture}
\vfill
\end{minipage}%
\hspace{0.3cm}
\begin{minipage}{.31\textwidth}
\centering
\begin{tikzpicture}[scale=0.8]
    \draw[dashed,black,fill=green!20] (1,-1) rectangle (2,-2);    
    \draw[black,very thick](-2,2) rectangle (2,-2);
      

    % Clusters
    \cluster{Cluster1}{1}{(1,1)};
	\cluster{Cluster2}{2}{(-1-0.3,1+0.3)};
	\cluster{Cluster3}{3}{(-1, -1)};	
	\cluster{Cluster4}{4}{(0, 0)};
\end{tikzpicture}
\vfill
\end{minipage}
\begin{minipage}{.31\textwidth}
\centering
\begin{tikzpicture}[scale=0.8]    
    \draw[dashed,black,fill=green!20] (-0.5,-1.5) rectangle (0.5,-2.5);    
    \draw[black,very thick](-1,2.5) rectangle (1,-2.5);
      

    % Clusters
    \cluster{Cluster1}{1}{(0, 2)};
	\cluster{Cluster2}{2}{(0, 1)};
	\cluster{Cluster3}{3}{(0, 0)};	
	\cluster{Cluster4}{4}{(0, -1)};
	
\end{tikzpicture}
\end{minipage}
\vskip20pt
\begin{minipage}{.31\textwidth}
\centering
{\footnotesize Uniform}
\end{minipage}
\hspace{0.10cm}
\begin{minipage}{.31\textwidth}
\centering
{\footnotesize Biased}
\end{minipage}
\hspace{0.02cm}
\begin{minipage}{.31\textwidth}
\centering
{\footnotesize Corridor}
\end{minipage}
\vfill
\end{frame}

\section{Results}

%16
\begin{frame}[t,fragile]{\textbf{Metrics}}
\begin{itemize}
\item<2,5> Allocated robots
\begin{equation}
R(t) = \sum_{i=1}^{20} (s_i(t)==\text{\emph{Allocation}}) 
\end{equation}
\item<3,5> Maximum error
\begin{equation}
e_{\max}(t) = \max_{i \in\{1,\cdots,4\}} e_i(t) = \max_{i \in\{1,\cdots,4\}} (r_i-o_i(t))
\end{equation}
\begin{equation}
e_{opt} = \lfloor \frac{m - n}{C} \rfloor + 1
\end{equation}
\item<4,5> Allocation level
\begin{align}
o_{x} = \underset{t}{\arg\min}(\bigwedge_{i=1}^{4} \frac{o_i(t)}{r_i} \ge x) &  & x \in {0.25,0.50} 
\end{align}
\end{itemize}
\end{frame}

%17
\begin{frame}[t,fragile]{\textbf{Allocation uniformity}}
\vskip10pt
To measure how evenly are the robot distributed across cluster we propose:
\vskip10pt
\begin{itemize}
\item<1-> Final maximum error  
\begin{equation}
e_{\max}(t_{ex})
\end{equation}
\vskip10pt
\item<2-> Cumulated probability to reach allocation level: 
\begin{align}
F_{o_{x}}(t_{ex}) = P[o_{x} \le t_{ex}] &  & x \in {0.25,0.50} 
\end{align}
\end{itemize}
\vskip10pt
where $t_{ex}$ corresponds to the experiment duration
\end{frame}

%18
\begin{frame}[t,fragile]{\textbf{Maximum error}}
\vskip15pt
\begin{center}
\begin{footnotesize}
\begin{tabular}{l c c c c c c}
\toprule % Top horizontal line
\textit{Method} & \multicolumn{6}{c}{\textit{Scenario}} \\ % Amalgamating several columns into one cell is done using the \multicolumn command as seen on this line
\cmidrule(l){2-7} % Horizontal line spanning less than the full width of the table - you can add (r) or (l) just before the opening curly bracket to shorten the rule on the left or right side
& \multicolumn{2}{c}{\textit{Uniform}} & \multicolumn{2}{c}{\textit{Biased}} & \multicolumn{2}{c}{\textit{Corridor}} \\ 
\textit{Statistic} & \textit{Median} & $(q_{25},q_{75})$ & \textit{Median} & $(q_{25},q_{75})$ & \textit{Median} & $(q_{25},q_{75})$ \\
\midrule
\midrule 
\textit{Naive} & 3 & (3,4) & 4 & (4,5) & 6 & (6,6) \\ 
\textit{Probabilistic} & 3 & (3,3) & 3 & (3,4) & 5 & (4,5) \\ 
\textit{Informed} & 3 & (3,3) & 3 & (3,3) & 5 & (4,5) \\ 
\midrule 
\bottomrule 
\end{tabular}
\end{footnotesize}
\vskip15pt
\begin{footnotesize}
\emph{Summary of the values of the maximum allocation error $e_{\max}(t)$ at t = 10000.

20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).

$e_{opt}=2$.}
\end{footnotesize}
\end{center}
\end{frame}


%19
\begin{frame}[t,fragile]{\textbf{Cumulated probability}}
\vskip20pt
\begin{center}
\begin{tabular}{l c c c c c c}
\toprule % Top horizontal line
\textit{Method} & \multicolumn{6}{c}{\textit{Scenario}} \\ % Amalgamating several columns into one cell is done using the \multicolumn command as seen on this line
\cmidrule(l){2-7} % Horizontal line spanning less than the full width of the table - you can add (r) or (l) just before the opening curly bracket to shorten the rule on the left or right side
& \multicolumn{2}{c}{\textit{Uniform}} & \multicolumn{2}{c}{\textit{Biased}} & \multicolumn{2}{c}{\textit{Corridor}} \\ 
\textit{Level} & 0.25 & 0.50 & 0.25 & 0.50 & 0.25 & 0.50 \\
\midrule
\midrule 
\textit{Naive} & 0.900 & 0.660 & 0.240 & 0.020 & 0.200 & 0.020 \\ 
\textit{Probabilistic} & 1.000 & 0.800 & 0.800 & 0.440 & 0.800 & 0.040 \\ 
\textit{Informed} & 1.000 & 0.740 & 0.900 & 0.680 & 0.800 & 0.060 \\ 
\midrule 
\bottomrule 
\end{tabular}
\vskip15pt
\begin{footnotesize}
\emph{Summary of the probabilities to reach allocation levels 25\% and 50\% 

within 10000 time steps.

20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).
}
\end{footnotesize}
\end{center}
\end{frame}

%20
\begin{frame}[t,fragile]{\textbf{Allocation speed}}
\vskip10pt
To measure the allocation speed of the methods we perform
a graphical comparison of:
\vskip10pt
\begin{itemize}
\item Allocated robots  
\begin{equation}
R(t)
\end{equation}
\vskip10pt
%\item Maximum error  
%\begin{equation}
%e_{\max}(t)
%\end{equation}
\vskip10pt
\item Allocation level cumulative distributions: 
\begin{align}
F_{o_{x}}(t) = P[o_{x} \le t] &  & x \in {0.25,0.50} 
\end{align}
\end{itemize}
\end{frame}

%\begin{frame}[t,fragile]{\textbf{Robots - Uniform vs Biased}}
%
%\begin{minipage}{.47\textwidth}
%\centering
%\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/A.Robots.Median.10000}.pdf}
%\end{minipage}%
%\hspace{0.15cm}
%\begin{minipage}{.47\textwidth}
%\centering
%\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/B.Robots.Median}.pdf}
%\end{minipage}
%\vfill
%\begin{scriptsize}
%\emph{Median values of the number of allocated robots $R(t)$ on the scenario Uniform (left) and Biased (right).
%
%20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).}
%\end{scriptsize}
%\end{frame}

\begin{frame}[t,fragile]{\textbf{Robots - Uniform vs Corridor}}

\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/A.Robots.Median.10000}.pdf}
\end{minipage}%
\hspace{0.15cm}
\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/C.Robots.Median}.pdf}
\end{minipage}
\vfill
\begin{scriptsize}
\emph{Median values of the number of allocated robots $R(t)$ on the scenario Uniform (left) and Corridor (right).

20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).}
\end{scriptsize}
\end{frame}

%21
\begin{frame}[t,fragile]{\textbf{Levels - Uniform vs Biased}}

\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/A.50}.pdf}
\end{minipage}%
\hspace{0.15cm}
\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/B.50}.pdf}
\end{minipage}
\vfill
\begin{scriptsize}
\emph{Empirical cumulative density functions for the allocation levels $o_{50}$ distributions of the three methods on the scenario Uniform (left) and Biased (right).

20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).}
\end{scriptsize}
\end{frame}

%22
\begin{frame}[t,fragile]{\textbf{Levels - Uniform vs Corridor}}

\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/A.50}.pdf}
\end{minipage}%
\hspace{0.15cm}
\begin{minipage}{.47\textwidth}
\centering
\includegraphics[width=\textwidth,keepaspectratio]{{../Figures/C.50}.pdf}
\end{minipage}
\vfill
\begin{scriptsize}
\emph{Empirical cumulative density functions for the allocation levels $o_{50}$ distributions of the three methods on the scenario Uniform (left) and Corridor (right).

20 e-pucks. 25 available tasks. 50 Trials. 10000 simulation steps per trial (1000s).}
\end{scriptsize}
\end{frame}

%23
\section{Conclusions}
\begin{frame}[t,fragile]{\textbf{Conclusions}}
\vskip10pt
\begin{itemize}
\item All the methods have minimal requirements and indirect communication among the robots.
\vskip7pt
\item \emph{Naive} achieves the fastest allocation...
\vskip7pt
\item ...but also the one having the lowest quality.
\vskip7pt
\item The probabilistic decision rule (\emph{Probabilistic} and \emph{Informed}) achieves a more uniform distribution.
\vskip7pt
\item Strong influence of the scenarios' topology on performances.
\vskip7pt
\item Space for improvement!
\end{itemize}

\note{
\begin{itemize}
\item Minimal requirements and no explicit communication among the robots.
\item Probabilistic allocation rule, even if simple, improves the
performance of the naive method.
\item Adding odometry does not bring particular improvements in
performance.
\item On some scenario the performance of the robots comes closer
to the optimal robot allocation.
\item Other scenarios are still to difficult to tackle for this simple
method.
\item Space for improvement!
\end{itemize}}

\end{frame}

%24
\begin{frame}[t,fragile]{\textbf{Future work}}
\vskip10pt
\begin{itemize}
\item Different probabilistic rules
\vskip10pt
\item Impact of direct communication (e.g. recruitment)
\vskip10pt
\item Flexibility, Scalability, Robustness tests
\vskip10pt
\item Experiments with real robots
\end{itemize}
\note{Tests:
\begin{itemize}
\item Flexibility - Change of the demands at a certain point in time and dynamic redistribution of the swarm
\item Scalability - Increase the number of robots and tasks
\item Robustness - With respect to errors in the measures 
\end{itemize}}
\end{frame}
